template<class T>
class LinearList
{
public:
	LinearList();
	~LinearList();
	virtual int Size()const = 0;   //get the max size of the list
	virtual int Length()const = 0;    //get the length of the list
	virtual int Search(T& x)const = 0;  //search "x" in the list
	virtual int Locate(int i)const = 0;   //locate i"th" element
	virtual bool getData(int i, T& x)const = 0;  //get the value of i"th" element
	virtual void setData(int i, T& x)const = 0;   //modify the value of i"th" element
	virtual bool Insert(int i, T& x)const = 0;     //insert element after i"th"
	virtual bool Remove(int i, T& x)const = 0;    //remove i"th" element
	virtual bool IsEmpty()const = 0;   //RT
	virtual bool IsFull()const = 0;   //RT
	virtual void Sort() = 0;       //RT
	virtual void input() = 0;     //RT
	virtual void output() = 0;    //RT
	
	virtual LinearList<T> operator = (LinearList<T>& L) = 0; //copy
};

template<class T>
struct LinkNode
{
	T data;
	LinkNode<T> *link;
	LinkNode(LinkNode<T> *ptr = 0)
	{ 
		link = ptr; 
	}
	LinkNode(const T&item, LinkNode<T> *ptr = 0)
	{
		data = item;
		link = ptr;
	}
};

template<class T>
class List : public LinearList < T >
{
public:
	List(){ first = new LinkNode < T > ;}   //constructor
	List(const T& x){ first = new LinkNode<T>(x); }    //constructor
	List(List<T>& L);         //copy constructor   $$
	~List(){ makeEmpty(); }   //deconstructor
	void makEmpty();     //make the list empty  $$
	int Length()const;   //calculate the length of list  $$
	LinkNode<T> *getHead()const{ return first; }   //get list head node
	LinkNode<T> *Search(T x);     //search element x   $$
	LinkNode<T> *Locate(int i);    //search "i"th's address   $$
	bool getData(int i, T& x)const;    //get "i"th's value    $$
	void setData(int i, T& x);     //use x to change "i"th's value   $$
	bool Insert(int i, T& x);    //insert element x after "i"th    $$
	bool Remove(int i, T& x);     //delete "i"th,return "i"th's value with x   $$
	bool IsEmpty()const         //RT
	{
		return first->link == 0 ? true : false;
	}
	bool IsFull()const   //RT
	{
		return false;
	}
	void Sort();//RT  $$
	void input();//RT  $$
	void output();//RT  $$
	List<T>& operator=(List<T>& L);//RT  $$
protected:
	LinkNode<T> *first;
};

template<class T>
List<T>::List(List<T>& L)
{
	T value;
	LinkNode<T> *srcptr = L.getHead();
	LinkNode<T> *destptr = first = new LinkNode < T > ;
	while (srcptr->link != 0)
	{
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = 0;
}

template<class T>
void List<T>::makEmpty()
{
	LinkNode<T> *q;
	while (first->link != 0)
	{
		q = first->link;
		first->link = q->link;
		delete q;
	}
}

template<class T>
int List<T>::Length()const
{
	LinkNode<T> *p = first->link;
	int count = 0;
	while (p != 0)
	{
		p = p->link; 
		count++;
	}
	return count;
}

template<class T>
LinkNode<T> *List<T>::Search(T x)
{
	LinkNode<T> *current = first->link;
	while (current != 0)
	{
		if (current->data == x)
			break;
		else
			current = current->link;
	}
	return current;
}

template<class T>
LinkNode<T> *Locate(int i)
{
	if (i < 0)
		return 0;
	LinkNode<T> *current = first;
	int k = 0;
	while (current != 0 && k < i)
	{
		current = current->link;
		++k;
	}
	return current;
}

template<class T>
bool List<T>::getData(int i, T& x)const
{
	if (i <= 0)
		return 0;
	LinkNode<T> *current = Locate(i);
	if (current == 0)
		return false;
	else
	{
		x = current->data;
		return true;
	}
}

template<class T>
void List<T>::setData(int i, T& x)
{
	if (i <= 0)
		return;
	LinkNode<T> *current = locate(i);
	if (current == 0)
		return;
	else
		current->data = x;
}

template<class T>
bool List<T>::Insert(int i, T& x)
{
	LinkNode<T> *current = locate(i);
	if (current == 0)
		return false;
	LinkNode<T> *newNode = new LinkNode<T>(x);   //constructor
	if (newNode == 0)
	{
		cerr << "error!" << endl;
		exit(1);
	}
	newNode->link = current->link;
	current->link = newNode;
	return true;
}

template<class T>
bool List<T>::Remove(int i, T& x)
{
	LinkNode<T> *current = locate(i - 1);
	if (current == 0 || current->link == 0)
		return false;
	LinkNode<T> *del = current->link;
	current->link = del->link;
	x = del->data;
	delete del;
	return true;
}

template<class T>
void List<T>::output()
{
	LinkNode<T> *current = first->link;
	while (current != 0)
	{
		cout << current - data << endl;
		current = current->link;
	}
}

template<class T>
List<T>& List<T>::operator=(List<T>& L)
{
	T value;
	LInkNode<T> *srcptr = L.getHead();
	LinkNode<T> *destptr = first = new LinkNode < T > ;
	while (srcptr->link != 0)
	{
		value = srcptr->link->data;
		destptr->link = new LinkNode<T>(value);
		destptr = destptr->link;
		srcptr = srcptr->link;
	}
	destptr->link = 0;
	return *this;
}
